#ifdef DEBUG
  #include <iostream>
  #include <cassert>
  #define dout(x) std::cout << x
#else
  #define dout(x)
  #define assert(x)
#endif

#include <cstdio>

using namespace std;

struct edge {
  int from;
  int to;
  int cost;
  bool used;
  int reverseindex;
  edge(int _from = 0, int _to = 0, int _cost = 0, bool _used = false,
      int _reverseindex = 0) : from(_from), to(_to), cost(_cost), used(_used),
      reverseindex(_reverseindex) { }
};

const int maxn = 64;
const int maxm = 10000;
const int maxedges = 2 * (maxm + maxn);
const int maxvertices = 2 * maxn;

int n, m;
int numedges, numvertices;
int source, sink;
edge e[maxedges];
int edgeto[maxvertices];
int cost[maxvertices];

bool readinput();
void bellmanford();
void buildgraph();
int invertex(int x);
int outvertex(int x);

int main() {
  int instance = 0;
  while (readinput()) {
    ++instance;
    dout("################################################" << endl);
    dout("test case " << instance << endl);
    bellmanford();
    if (edgeto[outvertex(n - 1)] == -1) {
      dout("not reachable in first search" << endl);
      printf("Instance #%d: Not possible\n", instance);
      continue;
    }
    int sol = cost[sink];
    int cur = sink;
    while (cur != source) {
      e[edgeto[cur]].used = true;
      e[e[edgeto[cur]].reverseindex].used = false;
      cur = e[edgeto[cur]].from;
    }

    #ifdef DEBUG
      printf("edges before second bellmanford:\n");
      for(int ii = 0; ii < numedges; ++ii) {
        printf("  from: %d  to: %d  cost: %d  used: %d  reverse: %d\n",
            e[ii].from, e[ii].to, e[ii].cost, e[ii].used, e[ii].reverseindex);
      }
    #endif

    bellmanford();
    if (edgeto[outvertex(n - 1)] == -1) {
      dout("not reachable in second search" << endl);
      printf("Instance #%d: Not possible\n", instance);
      continue;
    }
    sol += cost[outvertex(n - 1)];
    printf("Instance #%d: %d\n", instance, sol);
  }
  return 0;
}

void bellmanford() {
  for (int ii = 0; ii < numvertices; ++ii) {
    cost[ii] = -1;
    edgeto[ii] = -1;
  }
  cost[source] = 0;
  for (int ii = 0; ii < numvertices; ++ii) {
    for (int jj = 0; jj < numedges; ++jj) {
      if (e[jj].used || cost[e[jj].from] == -1) {
        continue;
      }
      if (cost[e[jj].to] == -1
        || cost[e[jj].to] > cost[e[jj].from] + e[jj].cost) {
        cost[e[jj].to] = cost[e[jj].from] + e[jj].cost;
        edgeto[e[jj].to] = jj;
      }
    }
  }
}

bool readinput() {
  scanf("%d %d", &n, &m);
  if (n == 0 && m == 0) {
    return false;
  }
  numvertices = 2 * n;
  source = invertex(0);
  sink = outvertex(n - 1);
  numedges = 0;
  for (int ii = 0; ii < n; ++ii) {
    int count = 1;
    if (ii == 0 || ii == n - 1) {
      count = 2;
    }
    for (int jj = 0; jj < count; ++jj) {
      e[numedges] = edge(invertex(ii), outvertex(ii), 0, false, numedges + 1);
      ++numedges;
      e[numedges] = edge(outvertex(ii), invertex(ii), 0, true, numedges - 1);
      ++numedges;
    }
  }
  for (int ii = 0; ii < m; ++ii) {
    int from, to, cost;
    scanf("%d %d %d", &from, &to, &cost);
    e[numedges] = edge(outvertex(from), invertex(to), cost,
        false, numedges + 1);
    ++numedges;
    e[numedges] = edge(invertex(to), outvertex(from), -cost,
        true, numedges - 1);
    ++numedges;
  }
  assert(numedges == 2 * m + 2 * n + 4);
  return true;
}

int invertex(int x) {
  return x; 
}

int outvertex(int x) {
  return x + n;
}
